#ifndef RBTREE_H
#define RBTREE_H
#pragma once
#include"TreeNode.h"

template<class T>
class RBTree
{
public:
	typedef TreeNode<T>* treen;
	treen root;
	
public:
	RBTree(T root_data);
	~RBTree();
	//插入
	void Add(T elem);
	//删除
	int Del(T elem);
	//查找后继
	TreeNode<T>* findNext(treen n);
	//左旋
	void leftRotate(treen n);
	//右旋
	void rightRotate(treen n);
	//调整颜色
	void Fix_color_Add(treen n);
	void Fix_color_Del(treen n);
	void colorFlip(treen n, treen uncle);
};

template<class T>
inline RBTree<T>::RBTree(T root_data): root(root) 
{
	this->root->data = root_data;
	this->root->color_tag = 0;//根节点必须为黑
}

template<class T>
inline RBTree<T>::~RBTree()
{
}

template<class T>
inline void RBTree<T>::Add(T elem)
{
	TreeNode<T>* temp = this->root;
	while (temp != NULL)
	{
		if (temp->data > elem)
			if (temp->Left == NULL)
			{
				temp->Left = new TreeNode<T>(elem);
				temp = temp->Left;
				Fix_color_Add(temp);
				return;
			}
			else temp = temp->Left;
		else if (temp->data <elem)
		{
			if (temp->Right ==NULL)
			{
				temp->Right = new TreeNode<T>(elem);
				temp = temp->Right;
				Fix_color_Add(temp);
				return;
			}
			else temp->Left = NULL;
		}
		else return;
	}
}

template<class T>
inline int RBTree<T>::Del(T elem)
{
	TreeNode<T>* temp = root;
	while (temp)
	{
		if (temp->data > elem)temp = temp->Left;
		else if (temp->data < elem)temp = temp->Right;
		else break;
	}
	//如果找到了对应元素，进行下一步操作，没找到返回-1
	if (temp)
	{
		int color_tag = temp->color_tag;//先存下要删除的结点颜色，如果顶替的结点颜色为黑，则该结点也就变成了双黑结点
		if (temp->Left == NULL && temp->Right == NULL)
		{
			if (temp == temp->Parent->Left)temp->Parent->Left = NULL;
			else temp->Parent->Right = NULL;
			temp->Parent = NULL:
		}
		else if (temp->Left != NULL && temp->Right == NULL)
		{
			if (temp = temp->Parent->Left)
			{
				temp->Left->Parent = temp->Parent;
				temp->Parent->Left = temp->Left;
			}
			else
			{
				temp->Left->Parent = temp->Parent;
				temp->Parent->Right = temp->Left;
			}

			temp->Left->color_tag = 0;
			temp = temp->Left;
		}
		else if (temp->Left == NULL && temp->Right != NULL)
		{
			if (temp = temp->Parent->Left)
			{
				temp->Right->Parent = temp->Parent;
				temp->Parent->Left = temp->Right;
			}
			else
			{
				temp->Right->Parent = temp->Parent;
				temp->Parent->Right = temp->Right;
			}
			temp->Right->color_tag = 0;
			temp = temp->Right;
		}
		else
		{
			//当删除的结点满孩子时，不急着删除，先将该结点值与后继结点替换，将删除该结点变为删除该结点的后继位置，从而减少操作
			TreeNode<T>* next = findNext(temp);
			temp->data = next->data;
			color_tag = next->color_tag;
			if (next->Right)
			{
				next->Right->Parent = next->Parent;
				next->Parent->Left = next->Right;
			}
			next->Right->color_tag = 0;
			temp = next;
		}
		//验证是否为删除后该位置是否为双黑结点，若是则平衡红黑树
		if (color_tag == 0)
		{
			Fix_color_Del(temp);
		}
	}
	else return -1;
	return 1;
}

template<class T>
inline TreeNode<T>* RBTree<T>::findNext(TreeNode<T>* n)
{
	TreeNode<T>* temp = n->Right;
	while (temp != NULL)temp = temp->left;
	return temp;
}

template<class T>
inline void RBTree<T>::leftRotate(TreeNode<T>* n)
{
	TreeNode<T>* temp = n;
	if (temp->Parent->Left = temp)temp->Parent->left = temp->Right;
	else temp->Parent->right = temp->Right;
	temp->Right->Parent = temp->Parent;
	temp->Parent = temp->Right;
	temp->Right = temp->Parent->Left;
	temp = temp->Parent->Left;
}

template<class T>
inline void RBTree<T>::rightRotate(TreeNode<T>* n)
{
	TreeNode<T>* temp = n;
	if(temp = temp->Parent->Left)temp->Parent->Left = temp->Left;
	else temp->Parent->Right = temp->Left;
	temp->Left->Parent = temp->Parent;
	temp->Parent = temp->Left;
	temp->Left = temp->Parent->Right;
	temp->Parent->Right = temp;
}

template<class T>
inline void RBTree<T>::colorFlip(TreeNode<T>* n, TreeNode<T>* uncle)
{
	temp->parent->color_tag = 0;
	uncle->color_tag = 0;
	temp = uncle->Parent;
	temp->color_tag = 1;
}

template<class T>
inline void RBTree<T>::Fix_color_Add(TreeNode<T>* n)
{
	TreeNode<T>* temp = n;
	//插入结点的双亲为黑，p事儿没有
	if (temp->color_tag == 0)return;
	TreeNode<T>* uncle;
	//为红时，考虑三种情况
	//第一种，双亲结点的兄弟为红
	while (temp->Parent->color_tag)
	{
		if (temp == temp->Parent->Right)
		{
			if (temp->Parent == temp->Parent->Parent->Left)uncle = temp->Parent->Parent->Right;
			else uncle = temp->Parent->Parent->left;
			//情况1 当叔叔结点与双亲同为红色
			if(uncle->color_tag)colorFlip(temp, uncle);
			//情况2 双亲为红，自己为双亲的右结点，且双亲与叔叔不同色
			else
			{
				temp = temp->parent;
				leftRotate(temp);
			}		
		}
		else
		{
			if (temp->Parent == temp->Parent->Parent->Left)uncle = temp->Parent->Parent->Right;
			else uncle = temp->Parent->Parent->left;

			if (uncle->color_tag)colorFlip(temp, uncle);
			//情况3 双亲为红，自己为双亲的左结点，且双亲与叔叔不同色
			else 
			{
				temp->parent->color_tag = 0;
				temp->parent->parent->color_tag = 1;
				rightRotate(temp->Parent->parent);
			}
		}
	}
	//如果是根节点，直接变黑
	this->root->color_tag = 0;
}

template<class T>
inline void RBTree<T>::Fix_color_Del(treen n)
{
	// 解决双黑结点
	while(n!=root&&n->color_tag==0)
	{
		// 找到兄弟结点
		treen bro;
		treen par;
		par = n->Parent;
		if(n = par->Left)
		{
			bro = par->Right;
			if(bro->color_tag == 1)
			{
				//     黑
				// 双黑  红
				bro->color_tag=0;
				par->color_tag=1;
				leftRotate(par);
				bro = par->Right;
				//          黑
				// 	   红
				// 双黑  黑
			}
			else if(bro->Left->color_tag==0&&bro->Right->color_tag==0)
			{
				bro->color_tag=1;
				n=par;
			}
				//          黑
				// 	   未知
				// 双黑    红
				//       黑  黑
				// 此时如果出现双红，离开循环后会将上层红置为黑
			else
			{
				if(bro->Right->color_tag==0)
				{
				//          黑
				// 	   红
				// 双黑  黑
				//     红  黑
				//   黑  黑
					bro->color_tag=1;
					bro->Left->color_tag=0;
					rightRotate(bro);
				//          黑
				// 	   红
				// 双黑  黑
				//     黑  红
				//       黑  黑	
					bro = par->Right;
					bro->color_tag = bro->Parent->color_tag;
					bro->Parent->color_tag=0;
					bro->Right->color_tag=0;
					leftRotate(par)
				//          黑
				// 	   黑
				// 双黑  黑
				//     红  黑
				//   黑  黑	
					n=root;
				}
			}
		}
		else 
		{
			bro = par->Left;
			if(bro->color_tag==1)
			{
				//       黑
				//   红     双黑
				// 黑  黑
				par->color_tag =1;
				bro->color_tag=0;
				rightRotate(par);
				bro = par->Left;
				//       黑
				//  黑       红     
				//         黑  双黑
			}
			else if(bro->Left->color_tag==0&&bro->Right->color_tag==0)
			{
				bro->color_tag=1;
				n=par;
				//       黑
				//  黑       未知     
				//         红  双黑
				// 此时如果出现双红，离开循环后会将上层红置为黑
			}
			else
			{
				if(bro->Left->color_tag==0)
				{
					bro->Right->color_tag=0;
					bro->color_tag=1;
					leftRotate(bro);
					bro = par->Left;
				//       黑
				//  黑         红     
				//         黑    双黑
				//      红    黑
				//    黑  黑
				}
				bro->color_tag = par->color_tag;
				par->color_tag=0;
				bro->Left->color_tag = 0;
				rightRotate(par);
				n=root;
				//       黑
				//  黑         红     
				//         黑      黑
				//       黑  黑  黑  双黑 
			}
		}
	}
	n->color_tag =0;
}

#endif // !RBTREE_H